package Exp_3;

import java.util.Scanner;
/**
 * 图的邻接表表示
 */
public class ALGraph implements IGraph {
    private GraphKind kind;// 图的种类表示
    private int vexNum, arcNum;// 图的当前顶点和边数
    private VNode[] vexs;// 顶点
    private static boolean[] visited;//设置访问标志数组

    public ALGraph() {
        this(null, 0, 0, null);
    }

    public ALGraph(GraphKind kind, int vexNum, int arcNum, VNode[] vexs) {
        this.kind = kind;
        this.vexNum = vexNum;
        this.arcNum = arcNum;
        this.vexs = vexs;
    }

    // 创建图的方法
    public void createGraph() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入图的类型:");
        GraphKind kind = GraphKind.valueOf(sc.next());
        switch (kind) {
            case UDG:
                createUDG();// 构造有向图
                return;
            case DG:
                createDG();// 构造无向图
                return;
        }
    }

    // 创建有向图
    private void createUDG() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请分别输入图的顶点数、图的边数：");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        vexs = new VNode[vexNum];
        System.out.println("分别输入图的各顶点：");
        for (int v = 0; v < vexNum; v++)
            // 构造顶点向量
            vexs[v] = new VNode(sc.next());
        System.out.println("请输入各边的顶点：");
        for (int k = 0; k < arcNum; k++) {
            int v = locateVex(sc.next());// 弧尾
            int u = locateVex(sc.next());// 弧头
            addArc(v, u, 1);
        }
    }

    // 创建无向图
    private void createDG() {
        Scanner sc = new Scanner(System.in);
        System.out.println("请分别输入图的顶点数、图的边数：");
        vexNum = sc.nextInt();
        arcNum = sc.nextInt();
        vexs = new VNode[vexNum];
        System.out.println("分别输入图的各顶点：");
        for (int v = 0; v < vexNum; v++)
            // 构造顶点向量
            vexs[v] = new VNode(sc.next());
        System.out.println("请输入各边的顶点");
        for (int k = 0; k < arcNum; k++) {
            int v = locateVex(sc.next());// 弧尾
            int u = locateVex(sc.next());// 弧头
            addArc(v, u, 1);
            addArc(u, v, 1);
        }
    }


    // 在图中插入边
    public void addArc(int v, int u, int value) {
        ArcNode arc = new ArcNode(u, value);
        arc.nextArc = vexs[v].firstArc;
        vexs[v].firstArc = arc;
    }

    public int getVexNum() {
        return vexNum;
    }

    public int getArcNum() {
        return arcNum;
    }

    //给定顶点值,返回顶点位置
    public int locateVex(Object vex) {
        for (int v = 0; v < vexNum; v++)
            if (vexs[v].data.equals(vex))
                return v;
        return -1;
    }

    public VNode[] getVexs() {
        return vexs;
    }

    public GraphKind getKind() {
        return kind;
    }


    public Object getVex(int v) throws Exception {
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在!");
        return vexs[v].data;
    }

    //查找第一个临界点算法
    public int firstAdjVex(int v) throws Exception {
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在!");
        VNode vex = vexs[v];
        if (vex.firstArc != null)
            return vex.firstArc.adjVex;
        else
            return -1;
    }

    //查找下一个临界点算法
    public int nextAdjVex(int v, int w) throws Exception {
        if (v < 0 && v >= vexNum)
            throw new Exception("第" + v + "个顶点不存在!");
        VNode vex = vexs[v];
        ArcNode arcvw = null;
        for (ArcNode arc = vex.firstArc; arc != null; arc = arc.nextArc)
            if (arc.adjVex == w) {
                arcvw = arc;
                break;
            }
        if (arcvw != null && arcvw.nextArc != null)
            return arcvw.nextArc.adjVex;
        else
            return -1;
    }

    public void setArcNum(int arcNum) {
        this.arcNum = arcNum;
    }

    public void setKind(GraphKind kind) {
        this.kind = kind;
    }

    public void setVexNum(int vexNum) {
        this.vexNum = vexNum;
    }

    public void setVexs(VNode[] vexs) {
        this.vexs = vexs;
    }

    //图的广度优先搜索
    public static void BFSTraverse(IGraph G) throws Exception {

        visited = new boolean[G.getVexNum()];
        for (int v = 0; v < G.getVexNum(); v++)
            //访问标志数组初始化
            visited[v] = false;
        for (int v = 0; v < G.getVexNum(); v++)
            if (!visited[v])//v尚未访问
                BFS(G, v);
    }

    private static void BFS(IGraph G, int v) throws Exception {
        visited[v] = true;
        System.out.print(G.getVex(v).toString() + " ");
        LinkQueue Q = new LinkQueue();//辅助队列Q
        Q.offer(v);
        while (!Q.isEmpty()) {
            int u = (Integer) Q.pool();//队头元素出队列并赋值给u
            for (int w = G.firstAdjVex(u); w >= 0; w = G.nextAdjVex(u, w))
                if (!visited[w]) {
                    visited[w] = true;
                    System.out.print(G.getVex(w).toString() + " ");
                    Q.offer(w);
                }
        }

    }

    //图的深度优先
    public static void DFSTraverse(IGraph G) throws Exception {

        visited = new boolean[G.getVexNum()];
        for (int v = 0; v < G.getVexNum(); v++)
            //访问标志数组初始化
            visited[v] = false;
        for (int v = 0; v < G.getVexNum(); v++)
            if (!visited[v])//v尚未访问
                DFS(G, v);
    }

    public static void DFS(IGraph G, int v) throws Exception {
        //从第v个顶点出发递归地深度优先遍历图G
        visited[v] = true;
        System.out.print(G.getVex(v).toString() + " ");//访问地v个顶点
        for (int w = G.firstAdjVex(v); w >= 0; w = G.nextAdjVex(v, w))
            if (!visited[w])
                DFS(G, w);
    }

}
